/*
 * @lc app=leetcode.cn id=322 lang=typescript
 *
 * [322] 零钱兑换
 */

// @lc code=start

//  思想：动态规划：
//  dp[i] 表示所需的最少的硬币个数
//  dp[i] = min(dp[i - coin]) + 1  coin为coins中的取值

//  复杂度：O(nk) O(n)

function coinChange(coins: number[], amount: number): number {
    // 由于要比较最小值，因此初始值赋无穷大
    const dp = new Array(amount + 1).fill(Infinity)

    // base case
    dp[0] = 0
    // 状态转移
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            // 无法取到的值
            if (i - coin < 0) continue
            dp[i] = Math.min(dp[i], dp[i - coin] + 1)

        }
    }

    return dp[amount] == Infinity ? -1 : dp[amount]
};
// @lc code=end

console.log(coinChange([2], 3));
